package com.zx._12_算法.字节跳动面试题;

import com.zx._12_算法.Nums;

public class 堆排序 {

    public static void main(String[] args) {
        int[] nums = Nums.nums;
        int len = nums.length;
        // 1. 从最后一个非叶子节点开始往前遍历，调整为最小堆
        for (int i = len / 2 - 1; i >= 0; i--) {
            sort(nums, i, len);
        }

        // 2. 将调整后的最小堆数据放在最后一位上，依次往前，交换后，调整堆
        for (int i = len - 1; i > 0; i--) {
            swap(nums, 0, i);
            sort(nums, 0, i);
        }
        Nums.printDown();
    }

    public static void sort(int[] nums, int i, int len) {
        int head = nums[i];

        for (int k = 2 * i + 1; k < len; k = 2 * k + 1) {
            if (k + 1 < len && nums[k + 1] < nums[k]) {
                k++;// k+1是最小的
            }
            if (nums[k] < head) {
                swap(nums, i, k);
                i = k;
            } else {
                break;
            }
        }

    }


    public static void swap(int[] nums, int a, int b) {
        if (a != b) {
            nums[a] ^= nums[b];
            nums[b] ^= nums[a];
            nums[a] ^= nums[b];
        }
    }

}
